package com.yvon.service.demo.algorithm.offer;

/**
 * 二叉搜索树的后序遍历序列
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9833.%20%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97/README
 */
public class P33 {

    public static void main(String[] args) {
        int[] postorder = new int[] {1,3,2,6,5};
        Solution solution = new P33().new Solution();
        boolean b = solution.verifyPostorder(postorder);
        System.out.println(b);
    }

    class Solution {
        public boolean verifyPostorder(int[] postorder) {
            if (postorder == null || postorder.length < 2) {
                return true;
            }
            return dfs(postorder, 0, postorder.length -1);
        }

        public boolean dfs(int[] postorder, int i, int j) {
            if (i >= j) {
                return true;
            }
            int root = postorder[j];
            int p = i;
            // 获取第一个大于或者等于 root 等元素的位置
            while (postorder[p] < root) {
                p ++;
            }
            // 判断 p ~ j -1 这个范围是否存在小于root的元素
            for (int k = p; k < j; k++) {
                if (postorder[k] < root) {
                    return false;
                }
            }

            return dfs(postorder,i, p - 1) && dfs(postorder, p, j - 1);
        }
    }
}
